/*
	Proyecto 3 - SO3
	Sudoku MPI
	
	Integrantes:
	 Ariana Perez
	 Cesar Hernandez
	 Omar Omaña
*/
#include <stdio.h> 
#include <stdlib.h> 
#include <mpi.h>
#include "Cuadrado.h"
#include <list>
#include <cmath>
#include <iterator>
#include <signal.h>

#define CASILLAS 81
#define INICIALIZAR 0
#define MENSAJE 1
#define GET 2
#define SET 3
#define BARRIER 11

using namespace std;

list<Cuadrado> areas;
int rank, size;
bool matar = false;
int resultado;

// i, j = [0 - 8]
int getCoordenada(int i, int j) {
	MPI_Status status;
	MPI_Request request;
	
	int div = floor(9.0/size);
	int k = (floor(i/3.0)*3)+floor(j/3.0);
	int comp = floor((k+0.0)/div); 
	int pos = k%div;
	int buffer[2], result[1];
	int flag;
	
	if(comp >= size) {
		comp = size-1;
		pos = k%div+div;
	}
	if(comp == rank) {	
		list<Cuadrado>::iterator p = areas.begin();
		advance(p, pos);
		
		return (*p).getValor(i%3, j%3);
	} else {	// Se comunica con comp y le pide la coordenada i, j
		buffer[0] = i;
		buffer[1] = j;
		MPI_Isend(buffer, 2, MPI_INT, comp, GET, MPI_COMM_WORLD, &request);
		MPI_Irecv(result, 1, MPI_INT, comp, SET, MPI_COMM_WORLD, &request);
		MPI_Test(&request, &flag, &status);
		while(!flag) {
			if (matar){
				exit(0);
			}
			MPI_Test(&request, &flag, &status);
		}
		return result[0]; 
	}
}

void llenarAreas(int buffer[]) {
	Cuadrado auxiliar;
	int k = 0;
	while(k < CASILLAS && buffer[k] != -1) {
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				auxiliar.setValor(i, j, buffer[k]);
				k++;
			}
		}
		areas.push_back(auxiliar);
	}
}

void setCoordenada(int i, int j, int valor) {
	int div = floor(9.0/size);
	int k = (floor(i/3.0)*3)+floor(j/3.0);
	int comp = floor((k+0.0)/div); 
	int pos = k%div;
	
	if(comp >= size) {
		comp = size-1;
		pos = k%div+div;
	}
	if(comp == rank) {	// No puede setear coordenadas que no le pertenecen
		list<Cuadrado>::iterator p = areas.begin();
		advance(p, pos);
		
		(*p).setValor(i%3, j%3, valor);
	}
}

void setRandom(int i, int j) {
	int div = floor(9.0/size);
	int k = (floor(i/3.0)*3)+floor(j/3.0);
	int comp = floor((k+0.0)/div); 
	int pos = k%div;
	
	if(comp >= size) {
		comp = size-1;
		pos = k%div+div;
	}
	if(comp == rank) {	// No puede setear coordenadas que no le pertenecen
		list<Cuadrado>::iterator p = areas.begin();
		advance(p, pos);
		
		(*p).setRandom(i%3, j%3);
	}
}

/* 
 * Devuelve true si el valor es posible en esa 
 * ubicacion o false en caso contrario
 */
bool comprobar_valor(int x, int y, int valor){ 
	if(getCoordenada(x,y) > 0) return true;		// Ya esta seteado
	
	// Busco si el valor se encuentra horizontal o vertical
	for(int k = 0; k < 9; k++)
		if(getCoordenada(k, y) == valor || getCoordenada(x, k) == valor) 
			return false;
			
	// Busco dentro del cuadrado 3x3
	int istart = (x/3)*3;
	int jstart = (y/3)*3;

	for(int i = istart; i < istart+3; i++)
		for(int j = jstart; j < jstart+3; j++)
			if(getCoordenada(i, j) == valor) 
				return false;

	return true;
}

/*
 * Proceso que ejecuta un hilo para la comunicacion
 */
void* comunicacionMPI(void*) {
	int buffer[2];
	MPI_Status status, status2;
	MPI_Request request;
	int result[1];
	int flag, flag2;
	
	while(true) {
		// Se recibe mensaje de cualquier proceso
		MPI_Irecv(buffer, 2, MPI_INT, MPI_ANY_SOURCE, GET, MPI_COMM_WORLD, &request);
		
		MPI_Test(&request, &flag, &status);
		while(!flag) {
			MPI_Test(&request, &flag, &status);
			if (matar){
				exit(0);
			}
		}
		if(buffer[0] == -1) {
			matar = true;
			exit(0);
		}
		result[0] = getCoordenada(buffer[0], buffer[1]);
		MPI_Send(result, 1, MPI_INT, status.MPI_SOURCE, SET, MPI_COMM_WORLD);
	}
}

// Implementacion de una barrera MPI porque MPI_BARRIER no funciona
void barrera() {
	MPI_Status status;
	MPI_Request request, request1;
	int i, flag;
	
	if(rank == 0) {
		for(i = 1; i < size; i++) {
			MPI_Irecv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, BARRIER, MPI_COMM_WORLD, &request);
			MPI_Test(&request, &flag, &status);
			while(!flag) {
				if (matar){
					exit(0);
				}
				MPI_Test(&request, &flag, &status);
			}
		} 
		// Todos llegaron y se les envia que continuen
		for(i = 1; i < size; i++) {
			MPI_Isend(NULL, 0, MPI_INT, i, BARRIER, MPI_COMM_WORLD, &request);
		}
	} else {
		MPI_Isend(NULL, 0, MPI_INT, 0, BARRIER, MPI_COMM_WORLD, &request);
		MPI_Irecv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, BARRIER, MPI_COMM_WORLD, &request1);
		MPI_Test(&request1, &flag, &status);
		while(!flag) {
			if (matar){
				exit(0);
			}
			MPI_Test(&request1, &flag, &status);
		}
	}
}

int main (int argc, char** argv) {
	int i,j, flag; 
	FILE * pFile; 
	int array[9][9];	/** ESTE NO ES NECESARIO DESPUES DE TENER LA INTERFAZ */
	int buffer[CASILLAS];
	int error, provided;
	
	pthread_t hilo;	// Maneja la comunicacion MPI entre computadoras
  
	MPI_Request request, request1, request2[9];
	MPI_Status status;
	
	MPI_Init_thread(&argc, &argv, MPI_THREAD_MULTIPLE, &provided); /* starts MPI */
	
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);        /* get current process id */
	MPI_Comm_size(MPI_COMM_WORLD, &size);        /* get number of processes */
	
	srand((unsigned)time(0)); 
    
	int div = floor(9.0/size);
	int k = 0, count = 0;
	
	/* Solo el proceso 0 ejecuta la interfaz */
	if(rank == 0) {
		// Debe enviarle a los demas las areas que le tocan a cada uno
		// y los procesos con los que debe comunicarse
		
		/** SOLO SIN INTERFAZ */
		pFile = fopen ("prueba.txt","r+"); 
		for (i = 0; i < 9; i++) { 
			error = fscanf (pFile, "%d %d %d %d %d %d %d %d %d",  
			&array[i][0],&array[i][1], &array[i][2], 
			&array[i][3],&array[i][4], &array[i][5], 
			&array[i][6],&array[i][7], &array[i][8]); 
		} 
		fclose (pFile); 
		/* Division del tablero */
		int r = 0;
		// Se llenan de izquierda a derecha y hacia abajo
		for(int x = 0; x < 3; x++) { 
			for(int y = 0; y < 3; y++) {
				for (i = 0; i < 3; i++) {  
					for (j = 0; j < 3; j++) { 
						buffer[k] = array[i+(x*3)][j+(y*3)];
						k++;
					}
				};
				count++;
				if(count == div && r < (size-1)) {
					count = 0;
					while(k < CASILLAS) {
						buffer[k] = -1;
						k++;
					}
					if(r == rank) llenarAreas(buffer);
					else {	// Se envia la informacion
						MPI_Send(buffer, CASILLAS, MPI_INT, r, INICIALIZAR, MPI_COMM_WORLD);
					}
					k = 0;
					r++;
				}
			}
		}
		while(k < CASILLAS) {
			buffer[k] = -1;
			k++;
		}
		if(r == rank) llenarAreas(buffer);
		else {	// Se envia la informacion
			MPI_Send(buffer, CASILLAS, MPI_INT, r, INICIALIZAR, MPI_COMM_WORLD);
		}				
	} else {
		// Debe recibir las areas que le toca resolver
		MPI_Recv(buffer, CASILLAS, MPI_INT, 0, INICIALIZAR, MPI_COMM_WORLD, &status);
		llenarAreas(buffer);
	}
	
	error = pthread_create(&hilo, NULL, comunicacionMPI, NULL);
	if (error) {
	  printf("Error, %d\n", error);
	  MPI_Finalize();
	  exit(-1);
	}
	
	barrera(); 	// Se espera a que todos lleguen
	
	// Se resuelve el sudoku...
	list<Cuadrado>::iterator p;
	list<int>::iterator q;
	list<int> posibles;
	int pos, maxi, maxj;
	bool setAll = false, setRand;
	int xrand, yrand, tam;
	int buff[2], reply[2], say[2];
	int numDone;
	
	while(true) {
		// Se eliminan posibilidades
		setRand = true;
		count = 9;
		flag = 0;
		if(!setAll) {
			setAll = true;
			for(p = areas.begin(); p != areas.end(); p++) {
				pos = distance(areas.begin(), p) + (rank*div);
				maxi = floor(pos/3.0)*3;
				maxj = (pos%3)*3;
				for(i = maxi; i < (maxi+3); i++) {
					for(j = maxj; j < (maxj+3); j++) {
						posibles = (*p).getPosibles(i%3, j%3);
						
						if(posibles.size() > 1) {
							for(q = posibles.begin(); q != posibles.end(); q++) {
								if(!comprobar_valor(i, j, *q)) 
									(*p).noPosible(i%3, j%3, *q);
							}
							tam = (*p).getPosibles(i%3,j%3).size();
							if(tam == 0) {
								printf("El sudoku NO tiene solucion\n");
								buff[0] = -1;
								for(int l = 0; l < size; l++)
									MPI_Isend(buff, 2, MPI_INT, l, GET, MPI_COMM_WORLD, &request);

								matar = true;
								exit(0);
							} else if (setRand == true && tam == 1) {
								setRand = false;
							} else if (setRand == false && count > tam) {
								count = tam;
								xrand = i;
								yrand = j;
								setAll = false;
							}
						}
					}
				}
			}
		}
		
		numDone = 0;
		// Se comunican para saber si alguno elige un
		// aleatorio o si ya se termino de resolver
		if(setAll) {
			say[0] = -1;
			numDone = 1;
			setRand = false;
		} else if(!setRand) {
			say[0] = 0;
			say[1] = -1;
		} else {
			say[0] = 0;
			say[1] = count;
		}
		for(i = 0; i < size; i++) {
			if(i == rank) continue;
			MPI_Isend(say, 2, MPI_INT, i, MENSAJE, MPI_COMM_WORLD, &request2[i]);
		}
		for(i = 0; i < size; i++) {
			if(i == rank) continue;
			MPI_Irecv(reply, 2, MPI_INT, i, MENSAJE, MPI_COMM_WORLD, &request1);
			MPI_Test(&request1, &flag, &status);
			while(!flag) {
				if (matar)
					exit(0);
					
				MPI_Test(&request1, &flag, &status);
			}
			if(reply[0] == -1) {
				numDone++;
			} else if(setRand) {
				if(count > reply[1] || (count == reply[1] && rank > i)) {
					setRand = false;
				}
			}
		}
		
		if(numDone == size) 
			break; // Se encontro una solucion!
		
		if(setRand)	{	// Selecciona un numero aleatorio entre los posibles
			setRandom(xrand, yrand);
		}
	}
	
	barrera();	// Se espera a que todos lleguen
	if(rank == 0) {
		printf("Resolucion Sudoku\n"); 
		for(i = 0; i < 9; i++) {
			for(j = 0; j < 9; j++) {
				printf("%d ",getCoordenada(i,j));
			}
			printf("\n");
		}
	}
	
	barrera();	// Se espera a que todos lleguen

	matar = true; // Finaliza el hilo

	MPI_Finalize();
	return 0;
}
